1. Field of the Invention
The present invention relates generally to data compression, and more particularly to a method to make efficient weighting of predictions of image colors at different image positions of for use in lossless image compression.
2. Discussion of Related Art Including Information Disclosed Under 37 CFR §§1.97, 1.98
Image compression is based on the generation of economical code. Colors at different image positions may be encoded using entropy coding methods in which color appearance probability distribution determines entropy codes. The efficiency of entropy encoding is almost the same as entropy of this distribution. Color appearance probability distribution at each image position can be predicted. Higher efficiency is achieved when prediction depends on information about already encoded/decoded colors at adjacent positions. Different combinations of already encoded/decoded data form informational contexts. Different contexts determine different predictions. In order to find generalized probability estimation different predictions may be combined using weighting: each prediction has its weight; weight determines significance of corresponding prediction; generalized probability distribution is calculated as a weighted superposition of probability distributions corresponding to different predictions.
Additionally, prediction weights can be used for calculation of weighted superposition of independent predictions of most probable value at each position to be processed (e.g. color value). Result of this superposition is a generalized prediction of most probable value. In many existing compression methods most probable values are of fundamental importance.
The determination of prediction weights is the main problem of weighted generalization. In order to make better predictions (for higher compression) it is necessary to rank predictions, so that more efficient predictions are given bigger weights. Prediction efficiency is determined by the size of corresponding entropy code. Entropy code size depends on the particular color value, which is considered as not available until it is processed during symmetrical data processing. Thus, code size is unknown a priori. It would be advantageous to find the method of a priori prediction ranking which gives the smallest possible code. Moreover, it is desirable that this ranking method is of low complexity so it could be used in practical applications.
The conventional approach for weighting of predictions entails the use of predefined static weights. Static weights can be assigned according to statistical results obtained beforehand, for example, during processing of some set of test images. More efficient dynamic ranking methods are based on collection of statistical information about efficiency of different predictions during image processing: weight of each prediction is a function of its efficiency in past. Weights could be also calculated with the use of color information from already processed image positions adjacent to the image position being processed or as a result of complicated learning (with the use of neural networks, weighted trees etc). Present method is based on simpler, but at the same time very efficient weighting solution. Weights are calculated using information about already known best predictions in close neighborhood of the position being processed. Indexes of known best predictions at already processed adjacent image positions form an auxiliary prediction context, which becomes a base for context-dependent prediction statistics collection. Number of times each particular prediction was the best prediction in past in current prediction context is treated as a prediction weight. Present context-based weighting method is a very effective solution for lossless image compression.
Further, the presently inventive method of prediction weighting can be used for prediction of samples of other data types; especially multidimensional.
Accordingly, the present invention provides a universal method that can be successfully used in many compression applications and applications related to forecasting.
It must be emphasized that while many other weighting solutions involve significant computational complexity, the present invention provides a better level of prediction efficiency and is incomparably fast due to its simplified procedure for weight determination.
In the case of limited computational resources, compression efficiency remains at the highest level when employing the present invention.
Further, because of prediction context formation flexibility, the present invention provides means to make prediction weighting while using a system having limited memory resources.